
/*
  给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
  输入：head = [1,2,3,4,5], n = 2
  输出：[1,2,3,5]
*/
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
// 可以先求出整条链表的长度，然后再让指针前进指定的步数，删除即可
var removeNthFromEnd = function (head, n) {
  let count = 0
  let p = cur = head
  const node = new ListNode(-1, head)
  let pre = node
  while (p) {
    p = p.next
    count++
  }
  for (let i = 0; i < count - n; i++) {
    pre = pre.next
    cur = cur.next
  }
  pre.next = cur.next
  cur = null
  return node.next
}

// 方法二：使用快慢指针，快指针先向前移动n个节点慢指针开始移动，当快指针指向空时，删除slow之后的元素
var removeNthFromEnd2 = function (head, n) {
  const virNode = new ListNode(-1, head)
  let slow = fast = virNode
  //  让fast指针先行n步
  while (n--) fast = fast.next
  // 这里让slow指向待删除节点的前一个，因此fast指向最后一个
  while (fast.next !== null) {
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next
  return virNode.next
}